﻿// homework5_problem1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
using namespace std;
//数组打印
void Print(int a[], int n)
{
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
}
int quickSortPartition(int s[], int l, int r) {
    //Swap(s[l], s[(l + r) / 2]); //若以中间数为基准，则先将中间的这个数和第一个数交换即可
    int i = l, j = r, x = s[l]; //将最左元素记录到x中
    while (i < j)
    {
        // 从右向左找第一个<x的数
        // 无需考虑下标越界
        while (i < j && s[j] >= x)
            j--;
        if (i < j)
            s[i++] = s[j]; //直接替换掉最左元素（已在x中存有备份）
        // 从左向右找第一个>x的数
        while (i < j && s[i] <= x)
            i++;
        if (i < j)
            //替换掉最右元素(已在最左元素中有备份）
            //最左元素一定被覆盖过，若没有，则表明右侧所有元素都>x，那么算法将终止
            s[j--] = s[i];
    }
    s[i] = x;  //i的位置放了x，所以其左侧都小于x，右侧y都大于x
    return i;
}

void quickSort(int s[], int l, int r)
{
    //数组左界<右界才有意义，否则说明都已排好，直接返回即可
    if (l >= r) {
        return;
    }
    // 划分，返回基准点位置
    int i = quickSortPartition(s, l, r);
    // 递归处理左右两部分，i处为分界点，不用管i了
    quickSort(s, l, i - 1);
    quickSort(s, i + 1, r);
}

int main()
{
    int a[100] = {};
    int num;
    int i;
    //printf("输入元素个数:\n");
    scanf("%d", &num);    //记得改成scanf提交!!!
    //printf("输入元素:\n");
    for (i = 0; i < num; i++) {
        scanf("%d", &a[i]);
    }
    quickSort(a, 0, num - 1); //注意最后一个参数是n-1
    Print(a, num);
    return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
